11295. Функция двух переменных

 

Для заданного целого числа n найдите наименьшее целое число x, удовлетворяющее двум условиям:

·        x больше или равно n;

·        Существует пара неотрицательных целых чисел (a, b), такая что

x = a3 + a2 * b + a * b2 + b3

 

Вход. Одно неотрицательное целое число n (n ≤ 1018).

 

Выход. Выведите наименьшее значение x.

 

Пример входа 1

Пример выхода 1

9

15

 

 

Пример входа 2

Пример выхода 2

0

0

 

 

РЕШЕНИЕ

перебор

 

Анализ алгоритма

Обозначим f(a, b) = a3 + a2 * b + a * b2 + b3. Функция f является возрастающей по а при фиксированном b и возрастающей по b при фиксированном а.

Поскольку n ≤ 1018, а функция f является кубической относительно а и b, то a ≤  = 106 и b ≤  = 106.

Требуемую пару (a, b) будем искать методом двух указателей, начиная с интервала [0; 106]. Установим a = 0, b = 106. Пока f(a, b) ≥ n и b неотрицательно, уменьшаем b на 1. Далее увеличим a на 1 и снова будем продолжать уменьшать b на 1 пока f(a, b) ≥ n и b ≥ 0. Процесс продолжаем пока a ≤ b.

 

Пример

Для n = 9 наименьшим искомым x будет 15. Например f(2, 1) = 15.

Для n = 0 искомым будет x = 0, так как f(0, 0) = 0.

 

Реализация алгоритма

Определим функцию f(a, b) = a3 + a2 * b + a * b2 + b3.

 

long long f(long long a, long long b)

{

  return (a * a * a + a * a * b + a * b * b + b * b * b);

}

 

Читаем входное значение n.

 

scanf("%lld", &n);

 

Инициализируем значение x.

 

x = 8e18;

 

Перебор начнем на интервале [0; 106], установив a = 0 и b = 106.

 

b = 1000000;

for (a = 0; a <= b; a++)

 

Пока f(a, b) ≥ n, уменьшаем значение b на 1 (пока b неотрицательно). Пересчитываем значение x.

 

  while (f(a, b) >= n && b >= 0)

  {

    x = min(x, f(a, b));

    b--;

  }

 

Выводим ответ.

 

printf("%lld\n", x);